#include <cmath>
#include <algorithm>
#include "CEditDistance.h"

const float eps = 1e-5;

float EditDistance::levenstein(const vector<int> &u, const vector<int> &v, int modCost){
    int sz1 = u.size();
    int sz2 = v.size();
    if(sz1==0 || sz2==0) return 1.0f;
    int* dis = computeDistance(u, v, modCost);
    int minDis = dis[sz1*sz2-1];
    //printf("min dis:%d\n", minDis);
    delete []dis;
    return 1.0f * minDis / (sz1 + sz2);
}

int EditDistance::accessDistance(int* dis, int sz2, int i, int j){
    if(i == -1 && j == -1) return 0;
    if(i == -1) return j + 1;
    if(j == -1) return i + 1;
    return dis[i * sz2 + j];
}


int* EditDistance::computeDistance(const vector<int> &u, const vector<int> &v, int modCost){
    int sz1 = u.size();
    int sz2 = v.size();
    if(sz1 == 0 || sz2 == 0) return nullptr;
    int *dis = new int[sz1*sz2];
    if(dis == nullptr) return nullptr;
    for(int i=0; i<sz1; i++){
        for(int j=0; j<sz2; j++){
            dis[i*sz2+j] = accessDistance(dis, sz2, i-1, j-1) + (u[i] != v[j]) * modCost;
            dis[i*sz2+j] = min(
                min(accessDistance(dis, sz2, i-1, j), accessDistance(dis, sz2, i, j-1)) + 1,
                dis[i*sz2+j]
            );
        }
    }
    //printf("\n");
    //for(int i=0; i<sz1; i++){
    //    for(int j=0; j<sz2; j++){
    //        printf("%d      ", dis[i*sz2+j]);
    //    }
    //    printf("\n");
    //}
    return dis;
}

vector<MatchingBlock> EditDistance::buildMatchingBlocks(const vector<int> &u, const vector<int> &v, int *dis, int modCost){
    int sz1 = u.size();
    int sz2 = v.size();
    vector<MatchingBlock> blocks;
    if(sz1==0 || sz2==0 || dis==nullptr) return blocks;


    int n = dis[sz1*sz2-1];
    bool inBlock = false;
    int uend = 0, vend = 0, len = 0;
    MatchingBlock mb;
    int dir = 0;
    // https://github.com/ztane/python-Levenshtein
    for(int i = sz1 - 1, j = sz2 - 1; n && (j >= 0 || i>=0); ){
        //printf("---------------\n%d, %d, %d, %d\n", i, j, dis[(i-1)*sz2+j], dis[i*sz2+j-1]);
        if(dir < 0 && dis[i*sz2+j] == accessDistance(dis, sz2, i, j-1) + 1){
            //printf("insert  %d, %d\n", i, j);
            if(inBlock){
                mb.ubeg = uend-len+1;
                mb.vbeg = vend-len+1;
                mb.len = len;
                inBlock = false;
                blocks.push_back(mb);
            }
            n--;
            j--;
            continue;
        }

        if(dir > 0 && dis[i*sz2+j] == accessDistance(dis, sz2, i-1, j) + 1){
            //printf("delete  %d, %d\n", i, j);
            if(inBlock){
                mb.ubeg = uend-len+1;
                mb.vbeg = vend-len+1;
                mb.len = len;
                inBlock = false;
                blocks.push_back(mb);
            }
            n--;
            i--;
            continue;
        }

        if(dis[i*sz2+j] == accessDistance(dis, sz2, i-1, j-1) && u[i]==v[j]){
            //printf("keep  %d, %d\n", i, j);
            if(!inBlock){
                uend = i;
                vend = j;
                len = 0;
                inBlock = true;
            }
            len++;
            i--;
            j--;
            dir = 0;
            continue;
        }

        if(dis[i*sz2+j] == accessDistance(dis, sz2, i-1, j-1) + modCost){
            //printf("modify  %d, %d\n", i, j);
            if(inBlock){
                mb.ubeg = uend-len+1;
                mb.vbeg = vend-len+1;
                mb.len = len;
                inBlock = false;
                blocks.push_back(mb);
            }
            n--;
            i--;
            j--;
            dir = 0;
            continue;
        }

        if(dir == 0 && dis[i*sz2+j] == accessDistance(dis, sz2, i, j-1) + 1){
            //printf("insert  %d, %d\n", i, j);
            if(inBlock){
                mb.ubeg = uend-len+1;
                mb.vbeg = vend-len+1;
                mb.len = len;
                inBlock = false;
                blocks.push_back(mb);
            }
            n--;
            j--;
            dir = -1;
            continue;
        }

        if(dir == 0 && dis[i*sz2+j] == accessDistance(dis, sz2, i-1, j) + 1){
            //printf("delete  %d, %d\n", i, j);
            if(inBlock){
                mb.ubeg = uend-len+1;
                mb.vbeg = vend-len+1;
                mb.len = len;
                inBlock = false;
                blocks.push_back(mb);
            }
            n--;
            i--;
            dir = 1;
            continue;
        }

        if(i * j <= 0){
            break;
        }else{
            //printf("ERROR: build matching block failed!\n");
            return blocks;
        }
    }

    if(inBlock){
        //printf("last block.");
        mb.ubeg = uend-len+1;
        mb.vbeg = vend-len+1;
        mb.len = len;
        blocks.push_back(mb);
    }
    delete[] dis;
    return blocks;
}

void print(vector<int> s){
    for(int i=0; i<s.size(); i++){
        if(i != s.size() - 1) printf("%d,", s[i]);
        else printf("%d", s[i]);
    }
    printf("\n");
}
float EditDistance::partialRatio(const vector<int> &u, const vector<int> &v){
    int sz1 = u.size();
    int sz2 = v.size();
    vector<int> shorter;
    vector<int> longer;
    if(sz1 < sz2){
        shorter = u;
        longer = v;
    }else{
        shorter = v;
        longer = u;
    }
    int *dis = computeDistance(shorter, longer, 2);
    vector<MatchingBlock> mbs = buildMatchingBlocks(shorter, longer, dis, 2);
    //printf("find matching blocks: %d\n", (int)mbs.size());
    int maxScore = 0.0f;
    for(int i = 0; i < mbs.size(); i++){
        //printf("%d, %d, %d\n",mbs[i].ubeg, mbs[i].vbeg, mbs[i].len);
        int start = mbs[i].vbeg > mbs[i].ubeg ? mbs[i].vbeg - mbs[i].ubeg : 0;
        int end = start + sz1;

        //print(shorter);
        //print(subVector(longer, start, end));
        float score = 1.0f - levenstein(shorter, subVector(longer, start, end), 2);
        //printf("%f\b", score);
        if(score > maxScore){
            maxScore = score;
        }
    }
    return maxScore;
}

float EditDistance::partialSortRatio(vector<int> u, vector<int> v){
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());
    return partialRatio(u, v);
}

float EditDistance::sortRatio(vector<int> u, vector<int> v){
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());
    return 1.0f - levenstein(u, v, 2);
}

vector<int> EditDistance::subVector(const vector<int> &v, int start, int end){
    vector<int> sub;
    for(int i = start; i < min((int)v.size(), end); i++){
        sub.push_back(v[i]);
    }
    return sub;
}
float EditDistance::tokenSetRatio(vector<int> u, vector<int> v){
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());
    removeSortRepeat(u);
    removeSortRepeat(v);

    vector<int> utov;
    vector<int> vtou;
    vector<int> intersec;
    for(int i=0, j=0; i < u.size() || j < v.size(); ){
        if(i< u.size() && j < v.size() && u[i] == v[j]){
            intersec.push_back(u[i]);
            i++;
            j++;
        }else if(i >= u.size() || (j < v.size() && u[i] > v[j])){
            vtou.push_back(v[j]);
            j++;
        }else{
            utov.push_back(u[i]);
            i++;
        }
    }
    vtou.insert(vtou.begin(), intersec.begin(), intersec.end());
    utov.insert(utov.begin(), intersec.begin(), intersec.end());
    //print(utov);
    //print(vtou);
    //print(intersec);
    return 1.0f - min(
            min(levenstein(intersec, vtou),
                levenstein(intersec, utov)
            ),
            levenstein(utov, vtou)
        );
}

void EditDistance::removeSortRepeat(vector<int> &u){
    int j=1;
    for(int i=1; i<u.size(); i++){
        if(u[i] != u[i-1]){
            u[j++] = u[i];
        }
    }
    while(u.size() > j) u.pop_back();
}

float EditDistance::getWeight(const std::vector<float> &weight, const int key, const std::vector<bool> &stop_words){
    if(key >= 0 && key < stop_words.size() && stop_words[key]) return 0.0f;
    if(weight.size() == 0) return 1.0f;
    if(key < 0 || key >= weight.size()) return 0.0f;
    return weight[key];
}

float EditDistance::wordMatch(std::vector<int> u, std::vector<int> v, const std::vector<bool> &stop_words, const std::vector<float> &weight){
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());
    removeSortRepeat(u);
    removeSortRepeat(v);
    float share_weight = 0;
    float total_weight = 0;
    for(int i=0; i<u.size(); i++){
        total_weight += getWeight(weight, u[i], stop_words);
        for(int j=0; j<v.size(); j++){
            if(i==0) total_weight += getWeight(weight, v[j], stop_words);
            if(u[i] == v[j]) share_weight += getWeight(weight, u[i], stop_words);
        }
    }
    return 2.0f * share_weight / (total_weight + eps);
}

// https://github.com/jamesturk/jellyfish
float EditDistance::jaroWinkler(const vector<int> &u, const vector<int> &v){
    int sz1 = u.size();
    int sz2 = v.size();
    int range = max(max(sz1, sz2) / 2 - 1, 0);
    int match = 0;
    vector<int> uMatch, vMatch;

    bool* hasMatched = new bool[sz2];
    for(int i = 0; i < sz2; i++) hasMatched[i] = false;

    for(int i=0; i < sz1; i++){
        for(int j = max(i-range, 0); j < min(i+range, sz2); j++){
            if(!hasMatched[j] && u[i] == v[j]){
                hasMatched[j] = true;
                uMatch.push_back(u[i]);
                match++;
                break;
            }
        }
    }

    if(!match) return 0.0f;
    //printf("match: %d\n", match);

    float trans = 0;
    for(int i=0, j=0; j<sz2; j++){
        if(hasMatched[j]){
            vMatch.push_back(v[j]);
            if(uMatch[i] != v[j]) trans += 1.0f;
            i++;
        }
    }
    trans /= 2.0f;
    //printf("trans: %f\n", trans);
    float jaro = (1.0f * match / sz1 + 1.0f * match / sz2 + 1.0f * (match - trans) / match) / 3;
    //printf("jaro: %f\n", jaro);

    int commPrefix = 0;
    if(jaro > 0.7f && sz1 >=4 && sz2 >= 4){
        for(int i = 0; i < min(4, min(sz1, sz2)); i++){
            if(u[i] == v[i]){
                commPrefix++;
            }else{
                break;
            }
        }
        //printf("comm prefix: %d\n", commPrefix);
        if(commPrefix) jaro += 0.1f * commPrefix * (1 - jaro);
    }

    return jaro;
}
